package com.ting.test.algorithms.大厂刷题班;

/**
 * 思路
 * 遍历求以i位置结尾的子数组中的最大累加和是多少
 * 比较返回其中最大的那个
 */
public class 数组中子数组最大累加和 {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 4, 5, 6, 8, 2, 1, 5, 7};
        int sum = process(arr);
    }

    private static int process(int[] arr) {
        if (arr == null) {
            return 0;
        }
        int pre = arr[0];//表示的是当前位置的前一个位置的最大累加和  0位置的最大累加和为arr[0];
        int max = pre;

        for (int i = 1; i < arr.length; i++) {
            // 有三种情况
            //1. 只有当前位置的元素
            //2. 从0到i不包含当前位置元素
            //3. 从0到i包含当前位置元素
            max = Math.max(Math.max(pre, pre + arr[i]), arr[i]);
            pre = max;
        }
        return max;
    }
}
